package com.leetcode.algorithm.topic;

/**
 * 字符串相关算法题解
 * 使用【双指针】技巧的典型场景之一：
 *  1.从两端向中间迭代数组。(一个指针从始端开始，而另一个指针从末端开始。)
 *  2.同时有一个慢指针和一个快指针。(关键:确定两个指针的移动策略。)
 * (done)67. 二进制求和
 * (done)14. 最长公共前缀
 * (TODO)28. 实现strStr():KMP算法
 * (done)344. 反转字符串
 * @author: jie.deng
 * @time: 2019年4月11日 上午9:15:26
 */
public class StringSolution {
    
    /**
     * 67. 二进制求和 
     * 给定两个二进制字符串，返回他们的和（用二进制表示）。
     * 输入为非空字符串且只包含数字 1 和 0。
     * 
     * 示例 1:
     * 输入: a = "11", b = "1" 
     * 输出: "100" 
     * 示例 2:
     * 输入: a = "1010", b = "1011" 
     * 输出: "10101"
     * 
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        if ("".equals(a)) {
            return b;
        } else if ("".equals(b)) {
            return a;
        }
        StringBuilder res = new StringBuilder();
        int la = a.length() - 1;
        int lb = b.length() - 1;
        int carry = 0;

        while (la >= 0 || lb >= 0) {
            int sum = carry;
            if (la >= 0) {
                sum += (a.charAt(la--) - '0');
            }
            if (lb >= 0) {
                sum += (b.charAt(lb--) - '0');
            }
            res.append(sum % 2);
            carry = sum >> 1;
        }
        if (carry != 0) {
            res.append(1);
        }
        return res.reverse().toString();
    }

    /**
     * 14. 最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * 
     * 示例 1:
     * 输入: ["flower","flow","flight"] 输出: "fl" 
     * 示例 2:
     * 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 
     * 说明:
     * 所有输入只包含小写字母 a-z 。
     * 
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null) {
            return "";
        }
        int len = strs.length;
        if (len == 0) {
            return "";
        }
        int minLen = strs[0].length();
        for (int i = 1; i < len; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }
        int idx = 0;
        outer: while (idx < minLen) {
            char ch = strs[0].charAt(idx);
            for (int i = 1; i < len; i++) {
                if (ch != strs[i].charAt(idx)) {
                    break outer;
                }
            }
            idx++;
        }
        return strs[0].substring(0, idx);
    }
    
    /**
     * 28. 实现strStr() 
     * 实现 strStr() 函数。
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置
     * (从0开始)。如果不存在，则返回 -1。
     * 
     * 示例 1:
     * 输入: haystack = "hello", needle = "ll" 输出: 2 
     * 示例 2:
     * 输入: haystack = "aaaaa", needle = "bba" 输出: -1 
     * 说明:
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     * 
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) { // needle是空字符串时返回 0
            return 0;
        }
        if (haystack.length() < needle.length()) {  //
            return -1;
        }
        int i = 0;
        char[] haystackChars = haystack.toCharArray();
        int haystackLen = haystackChars.length;
        char[] needleChars = needle.toCharArray();
        int needleCharsLen = needleChars.length;
        char ch = needleChars[0];
        while (i <= haystackLen - needleCharsLen) {//注意避免haystackChars[i + j]报数组越界异常
            if (haystackChars[i] == ch) {
                boolean matched = true;
                for (int j = 1; j < needleCharsLen; j++) {
                    if (haystackChars[i + j] != needleChars[j]) {
                        matched = false;
                        break;
                    }
                }
                if (matched) {
                    return i;
                }
            }
            i++;
        }
        return -1;
    }
    
    /**
     * 344. 反转字符串
     * 
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
     * 
     * 示例 1：
     * 
     * 输入：["h","e","l","l","o"]
     * 输出：["o","l","l","e","h"]
     * 示例 2：
     * 
     * 输入：["H","a","n","n","a","h"]
     * 输出：["h","a","n","n","a","H"]
     * @param s
     * @return
     */
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            char tmp = s[l];
            s[l++] = s[r];
            s[r--] = tmp;
        }
    }
    
}
